package code.mySpecializedTraining;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author 26029
 * @date 2025/4/24
 * @description
 */
public class SlideWindow {
    // 2799. 统计完全子数组的数目 4-24
    public int countCompleteSubarrays(int[] nums) {
        // 滑动窗口
        int n = nums.length;
        // 找到不同数字的数量
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        int diff_num = set.size();
        // map记录当前数字在滑动窗口中出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int ans = 0;
        // 如果[left, right]未达到条件，right++，继续增加数字
        // 如果[left, right]达到了条件，说明[left, n-1]都满足条件，答案＋(n-right)
        // 达到条件后，left++
        for (int right = 0; right < n; right++) {
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            // 未达到条件
            if (map.size() < diff_num) {
                continue;
            }
            // 达到条件 map.size() == diff_num
            while (map.size() == diff_num) {
                // 当前区间[l,r]以及[l,r+1],[l,r+2],...,[l,n-1]都是答案
                ans += n - right;
                // 左区间右移
                int leftNumCount = map.get(nums[left]);
                if (leftNumCount == 1)
                    map.remove(nums[left]);
                else
                    map.put(nums[left], leftNumCount - 1);
                left++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        SlideWindow slideWindow = new SlideWindow();
        System.out.println(slideWindow.countCompleteSubarrays(new int[]{1,3,1,2,2}));
    }
}
